from itertools import accumulate
from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:


        prefix_sum = [0]+list(accumulate(nums))
        
        all_result = defaultdict(int) # 区间的所有取值
        all_result[0] = 1
        result = 0
        # 求解两数之差(两数之和模板)
        for i in range(1,len(prefix_sum)):
            result += all_result[prefix_sum[i]-k]
            all_result[prefix_sum[i]] += 1
            
        return result


if __name__ == "__main__":
    s = Solution()
    r = s.subarraySum(nums = [1,1,1], k = 2)
    print(r)